package Ali;


import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author zhangmin
 * @create 2022-04-07 10:03
 */


public class Ali_0406_levelOrder {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int v){
            this.val=v;
        }
        TreeNode(int v,TreeNode l,TreeNode r){
            this.val=v;
            this.left=l;
            this.right=r;
        }
    }
    static List<List<Integer>> levelOrder(TreeNode root){
        List<List<Integer>> res=new LinkedList<>();
        if (root==null){
            return res;
        }
        Queue<TreeNode> q=new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()){
            int size=q.size();
            List<Integer> level=new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur=q.poll();
                level.add(cur.val);
                if (cur.left!=null){
                    q.add(cur.left);
                }
                if (cur.right!=null){
                    q.add(cur.right);
                }
            }
            res.add(level);
        }
        return res;
    }

    static boolean isMatch(List<List<Integer>> list1,List<List<Integer>> list2){
        //为了通用，需要判断空指针
        if (list1==null&&list2==null){
            return true;
        }
        if (list1==null||list2==null||list1.size()!=list2.size()){
            return false;
        }
        for (int i = 0; i < list1.size(); i++) {
            List<Integer> l1 = list1.get(i);
            List<Integer> l2 = list2.get(i);
            if (l1==null&&l2==null){
                continue;
            }
            if (l1==null||l2==null||l1.size()!= l2.size()){
                return false;
            }
            for (int j = 0; j < l1.size(); j++) {
                if (!l1.get(j).equals(l2.get(j))){ //要用equals，因为list是Integer包装类
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        //用例1：
        TreeNode root1=null;
        List<List<Integer>> result1 =new LinkedList<>();
        List<List<Integer>> res1 = levelOrder(root1);
        System.out.println(isMatch(result1,res1));

        //用例2
        TreeNode root2=new TreeNode(0,new TreeNode(1),new TreeNode(2,new TreeNode(3),null));
        List<List<Integer>> result2 =new LinkedList<>();
        result2.add(Arrays.asList(0));
        result2.add(Arrays.asList(1,2));
        result2.add(Arrays.asList(3));
        List<List<Integer>> res2 = levelOrder(root2);
        System.out.println(isMatch(result2,res2));
    }
}
